#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

# preorderVisitor: print node.val
# static void VisitInO1Memory (Node root, Action<Node> preorderVisitor)
# {
#   Node cur = root ;
#   Node left_max_maybe  = null ;

#   while (cur != null)
#   {
#         Node left_max = cur.left ;

#         if (left_max != null)
#         {
#             // search for thread
#             while (left_max != left_max_maybe && left_max.right != null)
#               left_max = left_max.right ;

#             if (left_max != left_max_maybe) {
#               // f1-1: connect cur's left_max to cur
#               assert left_max.right == null ;
#               left_max.right = cur ;

#               // f1-2: process cur
#               preorderVisitor (cur) ;

#               // f1-3: go to cur's left
#               cur = cur.left ;
#               continue ;
#             } else
#               // remove thread, left subtree of P already traversed
#               // this restores the node to original state
#               // f2-1: 断开 cur 和 left_max
#               left_max.right = null ;
#         }
#         else
#             // f3: 处理cur
#             preorderVisitor (cur) ;

#         // 两种情况会往right节点去: 一种是当前是叶子节点, 一种是断开连接后
#         // f2-2:往当前right节点走去(real right + parent)
#         left_max_maybe  = cur ;
#         // f2-3: 处理父节点的右边节点
#         cur = cur.right ;
#   }
# }


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class BSTIterator:
    def __init__(self, root):
        self.cur = root
        self.left_max_maybe = None
        self._push(root)

    def hasNext(self):
        return bool(self.cur)

    def _push(self, node):
        if not node:
            self.cur = node
            return

        while node.left:
            left_max = self._find_left_max_of(node, None)
            left_max.right = node
            print("left_max %s, node %s" % (left_max.val, node.val))
            node = node.left

        self.cur = node
        print('in _push cur %s' % self.cur.val)

    def next(self):
        # 先序遍历
        ret = self.cur

        self.left_max_may = self.cur
        may_cur = self.cur.right
        print('cur     %s' % self.cur.val)
        if not may_cur:
            self.cur = None
            return ret

        print('may_cur %s' % may_cur.val)
        if self._find_left_max_of(may_cur, self.left_max_may) == self.left_max_may:
            # 如果right是手动构造的比自己大的最小祖宗节点:表明祖宗节点左子树遍历完了, 接着该处理此祖宗节点: may_cur
            self.left_max_may.right = None
            self.cur = may_cur
            print('match pseudo right')
        else:
            # 否则应该_push 真正的right节点(因为right节点可能还有更多的left)
            print('not match pseudo right')
            max = self._find_left_max_of(may_cur,self.left_max_may)
            if max:
                print("find max %s" % max.val)
            else:
                print("find max %s" % max)
            self._push(may_cur)

        # 把self.left_max_may 和 self.cur之间手动connect断掉

        return ret

    # 以下是中序遍历
    # def next(self, ):
    #     ret = None

    #     if not self.cur.left:
    #         # 没有左节点: 处理当前节点
    #         # print('has not left of %s', self.cur.val)
    #         ret = self.cur
    #         self._drive_cur_to_available_right()      # right到一个可用节点: 保证每次self.cur可用, 或者到None, 表示has no next
    #         return ret

    #     # 有左节点
    #     left_max = self._find_left_max_of(self.cur, self.left_max_maybe)
    #     if left_max != self.left_max_maybe:
    #         # print('left_max is %s of %s' % (left_max.val, self.cur.val))
    #         # 连接 left_most_max and cur
    #         left_max.right= self.cur
    #         ret = self.cur
    #         self._drive_cur_to_left()
    #         return ret
    #     # else:
    #     #     # 断开, 恢复原先连接
    #     #     left_max.right = None

    # def _drive_cur_to_left(self):
    #     self.cur = self.cur.left

    # def _drive_cur_to_available_right(self):
    #     # 一直到right, 并断开, 直到self.cur可用

    #     self.left_max_maybe = self.cur
    #     self.cur = self.cur.right
    #     # print('updated : cur %s' % self.cur.val)

    #     while self.cur:
    #         if self._find_left_max_of(self.cur, self.left_max_maybe) != self.left_max_maybe:
    #             break

    #         # print('pseudo right match ...')
    #         self.left_max_maybe.right = None
    #         self.left_max_maybe = self.cur
    #         self.cur = self.cur.right

    def _find_left_max_of(self, node, maybe):
        if not node:
            return None

        left_max = node.left
        while left_max and left_max.right and left_max != maybe:
            left_max = left_max.right

        return left_max


def build_tree():
    root = TreeNode(3)
    left_root = TreeNode(1)
    right_root = TreeNode(5)

    root.left, root.right = left_root, right_root

    l1, r1 = TreeNode(0), TreeNode(2)
    left_root.left, left_root.right = l1, r1

    l2, r2 = TreeNode(4), TreeNode(6)
    right_root.left, right_root.right = l2, r2
    return root


def main():
    print("start main")

    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n0 = TreeNode(0)
    n1.left = n0
    n1.right = n2

    iter = BSTIterator(build_tree())
    while iter.hasNext():
        node = iter.next()
        print(node.val)

if __name__ == "__main__":
    main()
